package leetcode.递归回溯BFSDFS;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * N皇后 DFS
 *
 * @author https://leetcode-cn.com/problems/n-queens/
 * @author https://mp.weixin.qq.com/s?__biz=MzIzMDc5Mjg4Mw==&mid=100000465&idx=1&sn=949cecc27bcbe6a62eb3c6efa2dedf72&chksm=68af490d5fd8c01bf423e8c33bc20995fa687d828f758c18ebc3c074ef627b12d16ef39baba0&scene=20#rd
 *
 * 分析题目可知一旦某一行放置一个皇后了，那么这一行、这一列以及左右对角线均不能存放任何皇后了
 *
 * 因此需要知道已放入的皇后所在的位置，以及左右对角线如何计算，还要状态数组存放之前操作的结果
 */
public class Test51N皇后 {
    /**
     * n 皇后，行、列数都是 n
     * 设 rowIndex 表示行号，i 表示列号
     *
     * 左对角线计算公式：rowIndex + i  （左对角线上的坐标之和一样）
     * 右对角线计算公式：rowIndex - i + N - 1  （右对角线上的坐标之差一样）
     *      右对角线上的 X、Y 之差存在负数，我们希望数组从 0 开始，
     *          所以为了补偿负数需要加一个他的相反数，使其变为 0
     *              但是相反数是多少？不知道，但是可以通过输入的 N 来解决，就是上面的公式
     */

    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        if (n == 0)
            return result;
        // 用来标记皇后所在的列，便于下次遍历的时候直接跳过无用的递归
        boolean[] column = new boolean[n];
        // 2*n个斜对角线
        // 对角线设置为一维数组即可，因为同一条对角线上的这么多元素都有一个特征就是计算结果值相同
        boolean[] leftDiagonal = new boolean[2 * n];
        boolean[] rightDiagonal = new boolean[2 * n];
        backtrack(result, new ArrayList<>(), column, leftDiagonal, rightDiagonal, 0);
        return result;
    }

    private static void backtrack(List<List<String>> result, List<String> current,
                           boolean[] column, boolean[] leftDiagonal,
                           boolean[] rightDiagonal, int rowIndex) {
        // 回溯的条件
        int N = column.length;
        if (rowIndex == N) { // 已经处理到第N行了，说明皇后全部放置完毕
            result.add(new ArrayList<>(current));
            return;
        }

        // 遍历当前行的每一列
        for (int i = 0; i < N; i++) {
            // 发现本列、左右对角线不能存放皇后了，就需要让 i++ ，找一个新的地方再判断
            if (column[i] || leftDiagonal[rowIndex + i] || rightDiagonal[rowIndex - i + N - 1]) {
                continue;
            }

            // init 一个长度为 n 的一维数组，里面初始化为 '.'
            char[] charArray = new char[N];
            Arrays.fill(charArray, '.');
            // 当前位置允许放置皇后，就存入一个“Q”
            charArray[i] = 'Q';
            String stringArray = new String(charArray);
            current.add(stringArray);
            // 只要当前的行放下一个皇后,这一列、对角、反对角线都不能再放了.标记完后进行回溯
            column[i] = true;
            leftDiagonal[rowIndex + i] = true;
            rightDiagonal[rowIndex - i + N - 1] = true;

            /**
             * 假若一切顺利，一直递归下去就可以得到答案，
             * 但是若某一行无法存放一个皇后，则说明上一次放错了位置，需要重新放置，也就是回溯回去，列 + 1，再继续
             */
            backtrack(result, current, column, leftDiagonal, rightDiagonal, rowIndex + 1);

            // 如果上一次皇后的摆放位置有问题的话，就需要 reset，为了不影响回溯的下个目标
            current.remove(current.size() - 1);
            charArray[i] = '.';
            column[i] = false;
            leftDiagonal[rowIndex + i] = false;
            rightDiagonal[rowIndex - i + N - 1] = false;
        }
    }

    public static void main(String[] args) {
        List<List<String>> lists = solveNQueens(4);
        lists.forEach((e) -> System.out.println(e));
    }
}
